//给定一个非负整数数组 nums， nums 中一半整数是 奇数 ，一半整数是 偶数 。
//
// 对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。
//
// 你可以返回 任何满足上述条件的数组作为答案 。
//
//
//
// 示例 Array.prototype.unshift：
//
//
//输入：nums = [4,2,5,7]
//输出：[4,5,2,7]
//解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
//
//
// 示例 2：
//
//
//输入：nums = [2,3]
//输出：[2,3]
//
//
//
//
// 提示：
//
//
// 2 <= nums.length <= 2 * 10⁴
// nums.length 是偶数
// nums 中一半是偶数
// 0 <= nums[i] <= 1000
//
//
//
//
// 进阶：可以不使用额外空间解决问题吗？
//
// Related Topics 数组与矩阵 双指针 排序 👍 263 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
// 我的方法 无需申请空间 太慢
function sortArrayByParityII(nums: number[]): number[] {
    /*
    额外空间解法是：分成奇数组和偶数组 然后通过循环来组合成答案
    不用空间解法：双指针呗 还说啥呢
     */

    for (let i = 0, j; i < nums.length - 1; i ++) {
        j = i + 1
        // 偶
        if (i % 2 === 0) {
            // 但此时数字为奇
            if (nums[i] % 2 !== 0) {
                while (j < nums.length) {
                    if (nums[j] % 2 === 0) {
                        [nums[i], nums[j]] = [nums[j], nums[i]]
                    }
                    j ++
                }
            }
        }
        // 奇
        else {
            // 但此时数字为偶
            if (nums[i] % 2 !== 1) {
                while (j < nums.length) {
                    if (nums[j] % 2 === 1) {
                        [nums[i], nums[j]] = [nums[j], nums[i]]
                    }
                    j ++
                }
            }
        }
    }

    return nums
};
//leetcode submit region end(Prohibit modification and deletion)
// 这样不申请空间的方法更快
function sortArrayByParityII3(nums: number[]): number[] {
    /*
    额外空间解法是：分成奇数组和偶数组 然后通过循环来组合成答案
    不用空间解法：双指针呗 还说啥呢
     */

    const length: number = nums.length;
    let oddIndex: number = 1;
    for (let evenIndex = 0; evenIndex < length; evenIndex += 2) {
        if (nums[evenIndex] % 2 === 1) {// 在偶数位遇到了奇数
            while (oddIndex < length && nums[oddIndex] % 2 === 1) {// 在奇数位找一个偶数
                oddIndex += 2;
            }
            // 在奇数位找到了偶数，交换
            let temp = nums[evenIndex];
            nums[evenIndex] = nums[oddIndex];
            nums[oddIndex] = temp;
        }
    }
    return nums;
};


//leetcode submit region begin(Prohibit modification and deletion)
// 利用额外空间的方法
function sortArrayByParityII2(nums: number[]): number[] {
    /*
    额外空间解法是：分成奇数组和偶数组 然后通过循环来组合成答案
    不用空间解法：双指针呗 还说啥呢
     */

    const length: number = nums.length;
    const resArr: number[] = [];
    let evenIndex: number = 0,
        oddIndex: number = 1;
    for (let i = 0; i < length; i++) {
        if (nums[i] % 2 === 0) {
            resArr[evenIndex] = nums[i];
            evenIndex += 2;
        } else {
            resArr[oddIndex] = nums[i];
            oddIndex += 2;
        }
    }
    return resArr;
};
//leetcode submit region end(Prohibit modification and deletion)
